package leetcode.code0432;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class AllOne {

	Frequency head;
	Frequency tail;
	Map<String, Frequency> hash;

	public AllOne() {
		head = new Frequency();
		tail = new Frequency();
		head.next = tail;//
		tail.last = head;
		hash = new HashMap<>();
	}

	public void inc(String key) {
		if (hash.containsKey(key)) {
			// 出现过
			Frequency cur = hash.get(key);
			if (cur.next.count == 0 || cur.next.count != cur.count + 1) {
				// 需要新建下级节点
				Frequency next = new Frequency(cur.count + 1);
				cur.next.last = next;
				next.next = cur.next;
				next.last = cur;
				cur.next = next;
			}
			cur.next.set.add(key);
			hash.put(key, cur.next);
			cur.set.remove(key);
			if (cur.set.isEmpty()) {
				cur.last.next = cur.next;
				cur.next.last = cur.last;
			}
		} else {
			// 需要新建1级节点
			if (this.head.next.count == 1) {
				Frequency cur = this.head.next;
				cur.set.add(key);
				hash.put(key, cur);
			} else {
				Frequency next = new Frequency(1);
				this.head.next.last = next;
				next.next = this.head.next;
				next.last = this.head;
				this.head.next = next;
				next.set.add(key);
				hash.put(key, next);
			}
		}

	}

	public void dec(String key) {
		// 出现过
		Frequency cur = hash.get(key);
		if (cur.count == 1) {
			hash.remove(key);
			cur.set.remove(key);
			if (cur.set.isEmpty()) {
				cur.last.next = cur.next;
				cur.next.last = cur.last;
			}
			return;
		}
		if (cur.last.count != cur.count - 1) {
			// 需要新建上级节点
			Frequency last = new Frequency(cur.count - 1);
			cur.last.next = last;
			last.last = cur.last;
			last.next = cur;
			cur.last = last;
		}
		cur.set.remove(key);
		cur.last.set.add(key);
		hash.put(key, cur.last);
		if (cur.set.isEmpty()) {
			cur.last.next = cur.next;
			cur.next.last = cur.last;
		}

	}

	public String getMaxKey() {
		Frequency max = this.tail.last;
		if (max.count != 0) {
			return max.set.iterator().next();
		}
		return "";
	}

	public String getMinKey() {
		Frequency min = this.head.next;
		if (min.count != 0) {
			return min.set.iterator().next();
		}
		return "";
	}

	class Frequency {
		int count;
		Frequency last;
		Frequency next;
		Set<String> set;

		public Frequency() {
			count = 0;
			set = null;
		}

		public Frequency(int count) {
			this.set = new HashSet<>();
			this.count = count;
		}

	}

	public static void main(String[] args) {

//		 "inc","inc","dec","dec","dec","dec","getMaxKey",
//		 "inc","inc","inc","inc","inc","inc","getMaxKey","getMinKey"]
//		 ["hello"],["hello"],["world"],["leet"],["code"],["ds"],[],
		// ["new"],["new"],["new"],["new"],["new"],["new"],[],[]]
		AllOne allOne = new AllOne();
		allOne.inc("hello");
		allOne.inc("world");
		allOne.inc("leet");
		allOne.inc("code");
		allOne.inc("ds");
		allOne.inc("leet");
		String a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.inc("ds");
		allOne.dec("leet");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.dec("ds");
		allOne.inc("hello");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.inc("hello");
		allOne.inc("hello");
		allOne.dec("world");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.dec("leet");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.dec("code");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
		allOne.dec("ds");
		a = allOne.getMaxKey(); // 返回 "hello"
		System.out.println(a);
	}
}
